package main

func quick_sort(arr []int, startIndex, endIndex int)[]int{
	if startIndex >= endIndex{
		return arr
	}

	pivotIndex := partitionv2(arr, startIndex,endIndex)
	quick_sort(arr,startIndex, pivotIndex -1)
	quick_sort(arr, pivotIndex+1, endIndex)
	return arr
}

func partitionv2(arr []int, startIndex, endIndex int)int{

	var( mark = startIndex
	pivot = arr[startIndex]
	point = startIndex + 1
	)

	for point < len(arr){
		if arr[point] < pivot{
			mark ++
			arr[mark],arr[point] = arr[point],arr[mark]
		}
		point ++
	}
	arr[startIndex], arr[mark] = arr[mark], arr[startIndex]
	return mark
}
